#pragma once

namespace jianzhi_035
{

struct Node
{
    int val;
    Node* next;
    Node* random;
    explicit Node(int val) : val(val), next(nullptr), random(nullptr) {}
};

class Solution
{
public:
    Node* copyRandomList(Node* head)
    {
        if (head == nullptr)
            return nullptr;

        for (auto node = head; node != nullptr; ) {
            auto copy = new Node(node->val);
            copy->next = node->next;
            node->next = copy;
            node = copy->next;
        }

        for (auto node = head; node != nullptr; ) {
            auto copy = node->next;
            if (node->random)
                copy->random = node->random->next;
            node = copy->next;
        }

        auto head_copy = head->next;
        for (auto node = head; node != nullptr; ) {
            auto copy = node->next;
            auto next_node = copy->next;
            if (next_node)
                copy->next = next_node->next;
            node->next = next_node;
            node = next_node;
        }
        return head_copy;
    }
};

}  /* namespace jianzhi_035 */
